{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Artifacts That Can Be Extracted"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: digArtifacts"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计可以提取的工件"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>存在一个 <code>n x n</code> 大小、下标从 <strong>0</strong> 开始的网格，网格中埋着一些工件。给你一个整数 <code>n</code> 和一个下标从 <strong>0</strong> 开始的二维整数数组 <code>artifacts</code> ，<code>artifacts</code> 描述了矩形工件的位置，其中 <code>artifacts[i] = [r1<sub>i</sub>, c1<sub>i</sub>, r2<sub>i</sub>, c2<sub>i</sub>]</code> 表示第 <code>i</code> 个工件在子网格中的填埋情况：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>(r1<sub>i</sub>, c1<sub>i</sub>)</code> 是第 <code>i</code> 个工件 <strong>左上</strong> 单元格的坐标，且</li>\n",
    "\t<li><code>(r2<sub>i</sub>, c2<sub>i</sub>)</code> 是第 <code>i</code> 个工件 <strong>右下</strong> 单元格的坐标。</li>\n",
    "</ul>\n",
    "\n",
    "<p>你将会挖掘网格中的一些单元格，并清除其中的填埋物。如果单元格中埋着工件的一部分，那么该工件这一部分将会裸露出来。如果一个工件的所有部分都都裸露出来，你就可以提取该工件。</p>\n",
    "\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的二维整数数组 <code>dig</code> ，其中 <code>dig[i] = [r<sub>i</sub>, c<sub>i</sub>]</code> 表示你将会挖掘单元格 <code>(r<sub>i</sub>, c<sub>i</sub>)</code> ，返回你可以提取的工件数目。</p>\n",
    "\n",
    "<p>生成的测试用例满足：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>不存在重叠的两个工件。</li>\n",
    "\t<li>每个工件最多只覆盖 <code>4</code> 个单元格。</li>\n",
    "\t<li><code>dig</code> 中的元素互不相同。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2019/09/16/untitled-diagram.jpg\" style=\"width: 216px; height: 216px;\">\n",
    "<pre><strong>输入：</strong>n = 2, artifacts = [[0,0,0,0],[0,1,1,1]], dig = [[0,0],[0,1]]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong> \n",
    "不同颜色表示不同的工件。挖掘的单元格用 'D' 在网格中进行标记。\n",
    "有 1 个工件可以提取，即红色工件。\n",
    "蓝色工件在单元格 (1,1) 的部分尚未裸露出来，所以无法提取该工件。\n",
    "因此，返回 1 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2019/09/16/untitled-diagram-1.jpg\" style=\"width: 216px; height: 216px;\">\n",
    "<pre><strong>输入：</strong>n = 2, artifacts = [[0,0,0,0],[0,1,1,1]], dig = [[0,0],[0,1],[1,1]]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>红色工件和蓝色工件的所有部分都裸露出来（用 'D' 标记），都可以提取。因此，返回 2 。 \n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= artifacts.length, dig.length &lt;= min(n<sup>2</sup>, 10<sup>5</sup>)</code></li>\n",
    "\t<li><code>artifacts[i].length == 4</code></li>\n",
    "\t<li><code>dig[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= r1<sub>i</sub>, c1<sub>i</sub>, r2<sub>i</sub>, c2<sub>i</sub>, r<sub>i</sub>, c<sub>i</sub> &lt;= n - 1</code></li>\n",
    "\t<li><code>r1<sub>i</sub> &lt;= r2<sub>i</sub></code></li>\n",
    "\t<li><code>c1<sub>i</sub> &lt;= c2<sub>i</sub></code></li>\n",
    "\t<li>不存在重叠的两个工件</li>\n",
    "\t<li>每个工件 <strong>最多</strong> 只覆盖 <code>4</code> 个单元格</li>\n",
    "\t<li><code>dig</code> 中的元素互不相同</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-artifacts-that-can-be-extracted](https://leetcode.cn/problems/count-artifacts-that-can-be-extracted/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-artifacts-that-can-be-extracted](https://leetcode.cn/problems/count-artifacts-that-can-be-extracted/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2\\n[[0,0,0,0],[0,1,1,1]]\\n[[0,0],[0,1]]', '2\\n[[0,0,0,0],[0,1,1,1]]\\n[[0,0],[0,1],[1,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digArtifacts(self, n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int:\n",
    "        for i in range(len(dig)):\n",
    "            dig[i] = dig[i][0]*n+dig[i][1]\n",
    "        dig = set(dig)\n",
    "        ans = 0\n",
    "        for i in range(len(artifacts)):\n",
    "            flag = True\n",
    "            for x in range(artifacts[i][0],artifacts[i][2]+1):\n",
    "                for y in range(artifacts[i][1],artifacts[i][3]+1):\n",
    "                    if (x*n+y) not in dig:\n",
    "                        flag = False\n",
    "                        break\n",
    "            if flag:\n",
    "                ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digArtifacts(self, n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int:\n",
    "        # 二维前缀和吧\n",
    "        nums = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        for x, y in dig:\n",
    "            nums[x][y] = 1\n",
    "        \n",
    "        ans = 0\n",
    "        for r1, c1, r2, c2 in artifacts:\n",
    "            s = 1\n",
    "            for i in range(r1, r2+1):\n",
    "                for j in range(c1, c2+1):\n",
    "                    if nums[i][j] == 0:\n",
    "                        s = 0\n",
    "            ans += s\n",
    "        \n",
    "        return ans\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digArtifacts(self, n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int:\n",
    "        g = [[0] * n for _ in range(n)]\n",
    "        for x, y in dig:\n",
    "            g[x][y] += 1\n",
    "        ans = 0\n",
    "        for r1, c1, r2, c2 in artifacts:\n",
    "            if all(g[i][j] > 0 for i in range(r1, r2 + 1) for j in range(c1, c2 + 1)):\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 以空间换时间\n",
    "    def digArtifacts(self, n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int:\n",
    "        m=[]\n",
    "        for i in range(1005):\n",
    "            m.append([0 for x in range(1005)])\n",
    "        ans = 0\n",
    "        for d in dig:\n",
    "            m[d[0]][d[1]] = 1\n",
    "        for arti in artifacts:\n",
    "            r1, c1, r2, c2 = arti\n",
    "            flag = 1\n",
    "            for x in range(r1, r2+1):\n",
    "                for y in range(c1, c2+1):\n",
    "                    if m[x][y] == 0:\n",
    "                        flag = 0\n",
    "            if flag:\n",
    "                ans+=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digArtifacts(self, n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int:\n",
    "        digged = [[False]*n for _ in range(n)]\n",
    "        for r, c in dig:\n",
    "            digged[r][c] = True\n",
    "        ans = 0\n",
    "\n",
    "        def check(art):\n",
    "            r1, c1, r2, c2 = art\n",
    "            for r, c in product(range(r1, r2+1), range(c1, c2+1)):\n",
    "                if not digged[r][c]:\n",
    "                    return 0\n",
    "            return 1\n",
    "\n",
    "        return sum(map(check, artifacts))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digArtifacts(self, n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int:\n",
    "        digged = [[False]*n for _ in range(n)]\n",
    "        for r, c in dig:\n",
    "            digged[r][c] = True\n",
    "        ans = 0\n",
    "\n",
    "        def check(art):\n",
    "            r1, c1, r2, c2 = art\n",
    "            for r in range(r1, r2+1):\n",
    "                for c in range(c1, c2+1):\n",
    "                    if not digged[r][c]:\n",
    "                        return 0\n",
    "            return 1\n",
    "\n",
    "        return sum(map(check, artifacts))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digArtifacts(self, n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int:\n",
    "        digged = [[False]*n for _ in range(n)]\n",
    "        for r, c in dig:\n",
    "            digged[r][c] = True\n",
    "        ans = 0\n",
    "\n",
    "        def check(art):\n",
    "            r1, c1, r2, c2 = art\n",
    "            for r in range(r1, r2+1):\n",
    "                for c in range(c1, c2+1):\n",
    "                    if not digged[r][c]:\n",
    "                        return 0\n",
    "            return 1\n",
    "\n",
    "        return sum(map(check, artifacts))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digArtifacts(self, n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int:\n",
    "        digged = [[False]*n for _ in range(n)]\n",
    "        for r, c in dig:\n",
    "            digged[r][c] = True\n",
    "        ans = 0\n",
    "\n",
    "        def check(art):\n",
    "            r1, c1, r2, c2 = art\n",
    "            for r in range(r1, r2+1):\n",
    "                for c in range(c1, c2+1):\n",
    "                    if not digged[r][c]:\n",
    "                        return 0\n",
    "            return 1\n",
    "\n",
    "        return sum(map(check, artifacts))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digArtifacts(self, n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int:\n",
    "        digged = [[False]*n for _ in range(n)]\n",
    "        for r, c in dig:\n",
    "            digged[r][c] = True\n",
    "        ans = 0\n",
    "\n",
    "        def check(art):\n",
    "            r1, c1, r2, c2 = art\n",
    "            for r, c in product(range(r1, r2+1), range(c1, c2+1)):\n",
    "                if not digged[r][c]:\n",
    "                    return 0\n",
    "            return 1\n",
    "\n",
    "        return sum(map(check, artifacts))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digArtifacts(self, n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int:\n",
    "        undig = [[True]*n for _ in range(n)]\n",
    "        for r, c in dig:\n",
    "            undig[r][c] = False\n",
    "        ans = 0\n",
    "\n",
    "        def check(art):\n",
    "            r1, c1, r2, c2 = art\n",
    "            for r in range(r1, r2+1):\n",
    "                for c in range(c1, c2+1):\n",
    "                    if undig[r][c]:\n",
    "                        return 0\n",
    "            return 1\n",
    "\n",
    "        return sum(map(check, artifacts))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digArtifacts(self, n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int:\n",
    "        g = [[0] * n for _ in range(n)]\n",
    "        for r, c in dig:\n",
    "            g[r][c] = 1\n",
    "\n",
    "        ans = 0\n",
    "        for r1, c1, r2, c2 in artifacts:\n",
    "            can = True\n",
    "            for i in range(r1, r2 + 1):\n",
    "                if not can:\n",
    "                    break\n",
    "                for j in range(c1, c2 + 1):\n",
    "                    if not g[i][j]:\n",
    "                        can = False\n",
    "                        break\n",
    "            ans += int(can)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digArtifacts(self, n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int:\n",
    "        digged = [[False]*n for _ in range(n)]\n",
    "        for r, c in dig:\n",
    "            digged[r][c] = True\n",
    "        ans = 0\n",
    "\n",
    "        def check(art):\n",
    "            r1, c1, r2, c2 = art\n",
    "            for r in range(r1, r2+1):\n",
    "                for c in range(c1, c2+1):\n",
    "                    if not digged[r][c]:\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        return sum(map(check, artifacts))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digArtifacts(self, n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int:\n",
    "        digged = [[False]*n for _ in range(n)]\n",
    "        for r, c in dig:\n",
    "            digged[r][c] = True\n",
    "        ans = 0\n",
    "\n",
    "        def check(art):\n",
    "            r1, c1, r2, c2 = art\n",
    "            for r, c in product(range(r1, r2+1), range(c1, c2+1)):\n",
    "                if not digged[r][c]:\n",
    "                    return 0\n",
    "            return 1\n",
    "\n",
    "        return sum(map(check, artifacts))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digArtifacts(self, n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int:\n",
    "        q=[[False]*n for _ in range(n)]\n",
    "        for x,y in dig:\n",
    "            q[x][y]=True\n",
    "        ans=0    \n",
    "        for z1,r1,z2,r2 in artifacts:\n",
    "            a=False\n",
    "            for i in range(z1,z2+1):\n",
    "                if a:\n",
    "                           break \n",
    "                for j in range(r1,r2+1):\n",
    "                    if q[i][j]==False:\n",
    "                        a=True\n",
    "                        break\n",
    "            if not a:\n",
    "                ans+=1\n",
    "        return ans                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digArtifacts(self, n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int:\n",
    "        undig = [[True]*n for _ in range(n)]\n",
    "        for r, c in dig:\n",
    "            undig[r][c] = False\n",
    "        ans = 0\n",
    "\n",
    "        def check(art):\n",
    "            r1, c1, r2, c2 = art\n",
    "            for r in range(r1, r2+1):\n",
    "                for c in range(c1, c2+1):\n",
    "                    if undig[r][c]:\n",
    "                        return 0\n",
    "            return 1\n",
    "\n",
    "        return sum(map(check, artifacts))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digArtifacts(self, n: int, art: List[List[int]], dig: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        g = [[False] * n for _ in range(n)]\n",
    "        for x, y in dig:\n",
    "            g[x][y] = True\n",
    "        for r1, c1, r2, c2 in art:\n",
    "            flag = True\n",
    "            for i in range(r1, r2 + 1):\n",
    "                for j in range(c1, c2 + 1):\n",
    "                    if g[i][j] == False:\n",
    "                        flag = False\n",
    "                        break\n",
    "                if not flag:\n",
    "                    break\n",
    "            if flag:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digArtifacts(self, n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        mp = [[0]*n for i in range(n)]\n",
    "        for r,c in dig:\n",
    "            mp[r][c] = 1\n",
    "\n",
    "        def check(artifact):\n",
    "            r1,c1,r2,c2 = artifact\n",
    "            for r in range(r1, r2+1):\n",
    "                for c in range(c1, c2+1):\n",
    "                    if mp[r][c] != 1:\n",
    "                        return 0\n",
    "            return 1\n",
    "\n",
    "        for artifact in artifacts:\n",
    "            ans += check(artifact)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digArtifacts(self, n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int:\n",
    "        mat = [[0] * n for _ in range(n)]\n",
    "        for r,c in dig:\n",
    "            mat[r][c] = 1\n",
    "        ans= 0 \n",
    "        for [r1, c1, r2, c2] in artifacts:\n",
    "            flag = 1\n",
    "            for i in range(r1, r2+1):\n",
    "                for j in range(c1, c2+1):\n",
    "                    if mat[i][j] == 0:\n",
    "                        flag= 0\n",
    "                        break \n",
    "            if flag:\n",
    "                ans += 1 \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digArtifacts(self, n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int:\n",
    "        visited=[[0]*n for _ in range(n)]\n",
    "        index=1\n",
    "        res=0\n",
    "        for artifact in artifacts:\n",
    "            for i in range(artifact[0],artifact[2]+1):\n",
    "                for j in range(artifact[1],artifact[3]+1):\n",
    "                    visited[i][j]+=index\n",
    "            index+=1\n",
    "            \n",
    "        for i in range(len(dig)):\n",
    "            visited[dig[i][0]][dig[i][1]]=0\n",
    "        print(visited) \n",
    "        for artifact in artifacts:\n",
    "            flag=1\n",
    "            for i in range(artifact[0],artifact[2]+1):\n",
    "                for j in range(artifact[1],artifact[3]+1):\n",
    "                    if visited[i][j]!=0:\n",
    "                        flag=0\n",
    "            if flag==1:\n",
    "                res+=1\n",
    "        return res\n",
    "                        \n",
    "        \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digArtifacts(self, n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int:\n",
    "        m = len(artifacts)\n",
    "        cnt = [0] * m\n",
    "        grid = [[-1] * n for _ in range(n)]\n",
    "        total = [0] * m\n",
    "        for i, (x, y, z, w) in enumerate(artifacts):\n",
    "            s = 0\n",
    "            for j in range(x, z + 1):\n",
    "                for k in range(y, w + 1):\n",
    "                    grid[j][k] = i \n",
    "                    s += 1\n",
    "            total[i] = s \n",
    "\n",
    "        ans = 0\n",
    "        for x, y in dig:\n",
    "            c = grid[x][y]\n",
    "            if c == -1: continue\n",
    "            cnt[c] += 1\n",
    "            if cnt[c] == total[c]:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def digArtifacts(self, n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int:\n",
    "        # 初始化网格与未挖掘的部分计数器\n",
    "        grid = [[-1 for _ in range(n)] for _ in range(n)]\n",
    "        uncovered = [0] * len(artifacts)\n",
    "        \n",
    "        # 填充工件到网格，并设置未挖掘的部分计数器\n",
    "        for idx, (r1, c1, r2, c2) in enumerate(artifacts):\n",
    "            for i in range(r1, r2 + 1):\n",
    "                for j in range(c1, c2 + 1):\n",
    "                    grid[i][j] = idx\n",
    "                    uncovered[idx] += 1\n",
    "        \n",
    "        # 对于每次挖掘，更新未挖掘的部分计数器\n",
    "        artifacts_count = 0\n",
    "        for r, c in dig:\n",
    "            artifact_idx = grid[r][c]\n",
    "            if artifact_idx != -1: # 如果这个单元格有工件\n",
    "                uncovered[artifact_idx] -= 1\n",
    "                if uncovered[artifact_idx] == 0: # 如果这个工件完全被挖掘出来\n",
    "                    artifacts_count += 1\n",
    "                grid[r][c] = -1 # 移除工件的这一部分，避免多次计数\n",
    "        \n",
    "        return artifacts_count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 以空间换时间\n",
    "    def digArtifacts(self, n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int:\n",
    "        # m=[]\n",
    "        # for i in range(1005):\n",
    "        #     m.append([0 for x in range(1005)])\n",
    "        m=[[0 for x in range(1005)] for i in range(1005)]\n",
    "        ans = 0\n",
    "        for d in dig:\n",
    "            m[d[0]][d[1]] = 1\n",
    "        for arti in artifacts:\n",
    "            r1, c1, r2, c2 = arti\n",
    "            flag = 1\n",
    "            for x in range(r1, r2+1):\n",
    "                for y in range(c1, c2+1):\n",
    "                    if m[x][y] == 0:\n",
    "                        flag = 0\n",
    "            if flag:\n",
    "                ans+=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digArtifacts(self, n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int:\n",
    "        d = {}\n",
    "        res = 0\n",
    "        for x,y in dig:\n",
    "            d[x*1001+y] = 1\n",
    "        for x0,y0,x1,y1 in artifacts:\n",
    "            flag = True\n",
    "            for i in range(x0,x1+1):\n",
    "                for j in range(y0,y1+1):\n",
    "                    if (i*1001+j ) not in d:\n",
    "                        flag = False\n",
    "                        break\n",
    "            res += (1 if flag else 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digArtifacts(self, n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int:\n",
    "        setdig = {tuple(p) for p in dig}\n",
    "        return [all((r, c) in setdig for r in range(r1, r2 + 1) for c in range(c1, c2 + 1)) for r1, c1, r2, c2 in artifacts].count(True)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digArtifacts(self, n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int:\n",
    "        d = {tuple(pos) for pos in dig}\n",
    "        ans = 0\n",
    "        for (i, j, k, l) in artifacts:\n",
    "            is_dig = True\n",
    "            for x in range(i, k + 1):\n",
    "                for y in range(j, l + 1):\n",
    "                    if (x, y) not in d:\n",
    "                        is_dig = False\n",
    "                        break\n",
    "                if not is_dig: break\n",
    "            if is_dig: ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digArtifacts(self, n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int:\n",
    "        valid = {tuple(pos) for pos in dig}\n",
    "        \n",
    "        ans = 0\n",
    "        for (r1, c1, r2, c2) in artifacts:\n",
    "            check = True\n",
    "            for r in range(r1, r2 + 1):\n",
    "                for c in range(c1, c2 + 1):\n",
    "                    if (r, c) not in valid:\n",
    "                        check = False\n",
    "                        break\n",
    "                if not check:\n",
    "                    break\n",
    "            \n",
    "            if check:\n",
    "                ans += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digArtifacts(self, n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int:\n",
    "        valid = {tuple(pos) for pos in dig}\n",
    "        ans = 0\n",
    "        for(r1,c1,r2,c2) in artifacts:\n",
    "            check = True\n",
    "            for r in range(r1,r2+1):\n",
    "                for c in range(c1,c2+1):\n",
    "                    if (r,c) not in valid:\n",
    "                        check = False\n",
    "                        break\n",
    "                if not check:\n",
    "                    break\n",
    "            if check:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digArtifacts(self, n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int:\n",
    "        s=set()\n",
    "        ans=0\n",
    "        for i,j in dig:\n",
    "            s.add((i,j))\n",
    "        for a,b,c,d in artifacts:\n",
    "            check=True\n",
    "            for i in range(a,c+1):\n",
    "                for j in range(b,d+1):\n",
    "                    if (i,j) not in s:\n",
    "                        check=False\n",
    "            if check:\n",
    "                ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digArtifacts(self, n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int:\n",
    "        valid = {(r, c) for r, c in dig}\n",
    "        ans = 0\n",
    "\n",
    "        def check(art):\n",
    "            r1, c1, r2, c2 = art\n",
    "            for r in range(r1, r2+1):\n",
    "                for c in range(c1, c2+1):\n",
    "                    if (r, c) not in valid:\n",
    "                        return 0\n",
    "            return 1\n",
    "\n",
    "        return sum(map(check, artifacts))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digArtifacts(self, n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int:\n",
    "        valid = {*map(tuple, dig)}\n",
    "        ans = 0\n",
    "\n",
    "        def check(art):\n",
    "            r1, c1, r2, c2 = art\n",
    "            for r in range(r1, r2+1):\n",
    "                for c in range(c1, c2+1):\n",
    "                    if (r, c) not in valid:\n",
    "                        return 0\n",
    "            return 1\n",
    "\n",
    "        return sum(map(check, artifacts))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digArtifacts(self, n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int:\n",
    "        s=set()\n",
    "        ans=0\n",
    "        for i,j in dig:\n",
    "            s.add((i,j))\n",
    "        for a,b,c,d in artifacts:\n",
    "            check=True\n",
    "            for i in range(a,c+1):\n",
    "                for j in range(b,d+1):\n",
    "                    if (i,j) not in s:\n",
    "                        check=False\n",
    "                if not check:\n",
    "                    break\n",
    "            if check:\n",
    "                ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digArtifacts(self, n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int:\n",
    "        ans=0\n",
    "        s=set()\n",
    "        for a,b in dig:\n",
    "            s.add((a,b))\n",
    "        for a,b,c,d in artifacts:\n",
    "            if all((x,y) in s for x in range(a,c+1) for y in range(b,d+1)):\n",
    "                ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # * 哈希表\n",
    "    # 使用哈希表存储挖掘的位置\n",
    "    # 我们首先遍历数组 digs，并使用哈希集合存储其中的每一个位置。\n",
    "    # 随后我们遍历数组 artifacts 中的每一个工件，由于「每个工件最多只覆盖 4 个单元格」，我们可以直接遍历每一个工件的每一个单元格，如果该工件的所有单元格都在哈希集合中，我们就可以提取该工件。\n",
    "    def digArtifacts(self, n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int:\n",
    "        valid = {tuple(pos) for pos in dig}\n",
    "        \n",
    "        ans = 0\n",
    "        for (r1, c1, r2, c2) in artifacts:\n",
    "            check = True\n",
    "            for r in range(r1, r2 + 1):\n",
    "                for c in range(c1, c2 + 1):\n",
    "                    if (r, c) not in valid:\n",
    "                        check = False\n",
    "                        break\n",
    "\n",
    "                if not check:\n",
    "                    break\n",
    "            \n",
    "            if check:\n",
    "                ans += 1\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digArtifacts(self, n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int:\n",
    "        dct = {(a, b) for a, b in dig}\n",
    "        ans=0\n",
    "        def check():\n",
    "            for x in range(x1, x2+1):\n",
    "                for y in range(y1, y2+1):\n",
    "                    if (x, y) not in dct:\n",
    "                        return False\n",
    "            return True\n",
    "        \n",
    "        for x1,y1,x2,y2 in artifacts:\n",
    "            ans += check()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digArtifacts(self, n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int:\n",
    "        res = len(artifacts)\n",
    "        k = set()\n",
    "        for i in dig:\n",
    "            k.add(tuple(i))\n",
    "        for i in artifacts:\n",
    "            flag = 1\n",
    "            x0 = i[0]\n",
    "            y0 = i[1]\n",
    "            x1 = i[2]\n",
    "            y1 = i[3]\n",
    "            if (x0, y0) not in k or (x0, y1) not in k or (x1, y0) not in k or (x1, y1) not in k :\n",
    "                res -= 1\n",
    "            else:\n",
    "                for x in range(x0, x1+1):\n",
    "                    for y in range(y0, y1+1):\n",
    "                        if (x, y) not in k:\n",
    "                            res -= 1\n",
    "                            flag = 0\n",
    "                            break\n",
    "                    if flag == 0:\n",
    "                        break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digArtifacts(self, n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int:\n",
    "        dig = {tuple(pos) for pos in dig}\n",
    "        ans = 0\n",
    "        for art in artifacts:\n",
    "            l, r = art[0], art[2]\n",
    "            upper, low = art[1], art[3]\n",
    "            check = True\n",
    "            for i in range(l,r + 1):\n",
    "                for j in range(upper, low + 1):\n",
    "                    if (i,j) not in dig:\n",
    "                        check = False\n",
    "                        break\n",
    "                if not check:\n",
    "                    break\n",
    "            if check:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digArtifacts(self, n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int:\n",
    "        dig = set(tuple(pos) for pos in dig)\n",
    "        ans = 0\n",
    "        for art in artifacts:\n",
    "            l, r = art[0], art[2]\n",
    "            upper, low = art[1], art[3]\n",
    "            check = True\n",
    "            for i in range(l,r + 1):\n",
    "                for j in range(upper, low + 1):\n",
    "                    if (i,j) not in dig:\n",
    "                        check = False\n",
    "                        break\n",
    "                if not check:\n",
    "                    break\n",
    "            if check:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digArtifacts(self, n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int:\n",
    "        valid = {*map(tuple, dig)}\n",
    "        ans = 0\n",
    "\n",
    "        def check(art):\n",
    "            r1, c1, r2, c2 = art\n",
    "            for r in range(r1, r2+1):\n",
    "                for c in range(c1, c2+1):\n",
    "                    if (r, c) not in valid:\n",
    "                        return 0\n",
    "            return 1\n",
    "\n",
    "        return sum(map(check, artifacts))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # * 哈希表\n",
    "    # 使用哈希表存储挖掘的位置\n",
    "    # 我们首先遍历数组 digs，并使用哈希集合存储其中的每一个位置。\n",
    "    # 随后我们遍历数组 artifacts 中的每一个工件，由于「每个工件最多只覆盖 4 个单元格」，我们可以直接遍历每一个工件的每一个单元格，如果该工件的所有单元格都在哈希集合中，我们就可以提取该工件。\n",
    "    def digArtifacts1(self, n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int:\n",
    "        valid = {tuple(pos) for pos in dig}\n",
    "        \n",
    "        ans = 0\n",
    "        for (r1, c1, r2, c2) in artifacts:\n",
    "            check = True\n",
    "            for r in range(r1, r2 + 1):\n",
    "                for c in range(c1, c2 + 1):\n",
    "                    if (r, c) not in valid:\n",
    "                        check = False\n",
    "                        break\n",
    "\n",
    "                if not check:\n",
    "                    break\n",
    "            \n",
    "            if check:\n",
    "                ans += 1\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "    def digArtifacts(self, n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int:\n",
    "        cover = set()\n",
    "        for r, c in dig:\n",
    "            cover.add((r, c))\n",
    "\n",
    "        ans = 0\n",
    "        for r1, c1, r2, c2 in artifacts:\n",
    "            area = 0\n",
    "            for i in range(r1, r2 + 1):\n",
    "                for j in range(c1, c2 + 1):\n",
    "                    if (i, j) in cover:\n",
    "                        area += 1\n",
    "\n",
    "            if area == (r2 - r1 + 1) * (c2 - c1 + 1):\n",
    "                ans += 1\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digArtifacts(self, n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int:\n",
    "        dig = set(tuple(pos) for pos in dig)\n",
    "        ans = 0\n",
    "        for art in artifacts:\n",
    "            l, r = art[0], art[2]\n",
    "            upper, low = art[1], art[3]\n",
    "            cnt = 0\n",
    "            for i in range(l,r + 1):\n",
    "                for j in range(upper, low + 1):\n",
    "                    if (i,j) in dig:\n",
    "                        cnt += 1\n",
    "            if cnt == (r - l + 1) * (low - upper + 1):\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digArtifacts(self, n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int:\n",
    "        map = set([(a, b) for a, b in dig])\n",
    "        return sum(all((i, j) in map for i in range(r1, r2+1) for j in range(c1, c2+1)) for r1, c1, r2, c2 in artifacts)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digArtifacts(self, n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int:\n",
    "        d = dict()\n",
    "        dig = set([(x, y) for x, y in dig])\n",
    "        ret = 0\n",
    "        for k, (r1, c1, r2, c2) in enumerate(artifacts):\n",
    "            flag = 0\n",
    "            for i in range(r1, r2 + 1):\n",
    "                for j in range(c1, c2 + 1):\n",
    "                    if (i, j) not in dig:\n",
    "                        flag = 1\n",
    "                        break\n",
    "                if flag:\n",
    "                    break\n",
    "            else:\n",
    "                ret += 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digArtifacts(self, n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int:\n",
    "        digset=set()\n",
    "        for x in dig:\n",
    "            digset.add(tuple(x))\n",
    "        print(digset)\n",
    "        def helper(ly,lx,ry,rx):\n",
    "            for i in range(ly,ry+1):\n",
    "                for j in range(lx,rx+1):\n",
    "                    if (i,j) not in digset:\n",
    "                        return 0\n",
    "            return 1\n",
    "        return sum([ helper(*x) for x in artifacts])\n",
    "            "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
